The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We report on computer search for generalized Gosper curve for 37 < N < 61, where N is the degree of the generalized Gosper curve. From the results of the computer search and some geometrical insight, we conjecture that the degree N satisfies N = 6n + 1. We investigate the existence of infinite series of generalized Gosper curves. We show how to generate these series and introduce two new methods,...
An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Some results concerning k-contractible edges in a k-connected graph are presented.
Let G be a 2-connected weighted graph and m a nonnegative number. As introduced by Li as the weighted analogue of a concept due to Zhu et al, we use idw(v) to denote the implicit weighted degree of a vertex v in G. In this paper we prove that G contains either a Hamilton cycle or a cycle of weight at least m, if the following two conditions are satisfied: (1) max...
For every vertex v in a graph G, let L(v) denote a list of colors assigned to v. A list coloring is a proper coloring f such that f(v) ∈ L(v) for all v. A graph is k-choosable if it admits a list coloring for every list assignment L with |L(v)| = k. The choice number of G is the minimum k such that G is k-choosable. We generalize a result (of [4]) concerning the choice numbers of complete bipartite...
Let Pn be a set of n points on the plane in general position, n ≥ 4. A convex quadrangulation of Pn is a partitioning of the convex hull $\mathit{Conv}(P_n)$ of Pn into a set of quadrilaterals such that their vertices are elements of Pn, and no element...
Let G = (V, E) be an edge-colored graph. A matching of G is called heterochromatic if its any two edges have different colors. Unlike uncolored matchings for which the maximum matching problem is solvable in polynomial time, the maximum heterochromatic matching problem is NP-complete. This means that to find both sufficient and necessary good conditions for the existence of perfect heterochromatic...
Three partial orders, cut-size order, length order, and operation order, defined between labeled graphs with the same number of vertices are known to be equivalent. From the equivalence, G precedes G′ in the order means that there is a sequence of cross-operations transforming G into G′. However, even if both graphs are simple, non-simple graphs may appear on the way of the transformation. If both...
Let a, b, k, and m be positive integers such that 1 ≤ a < b and 2 ≤ k ≤ (b + 1 − m)/a. Let G = (V(G), E(G)) be a graph of order |G|. Suppose that |G| > (a + b)(k(a + b − 1) − 1)/b and |NG(x1) ∪ NG(x2) ∪ ⋯ ∪ NG(xk)| ≥ a|G|/(a + b...
Let R and B be two disjoint sets of red points and blue points, respectively, in the plane such that no three points of R ∪ B are co-linear. Suppose ag ≤ |R| ≤ (a + 1)g, bg ≤ |B| ≤ (b + 1)g. Then without loss of generality, we can express |R| = a(g1 + g2) + (a + 1)g3, |B| = bg1 + (b + 1)(g2 + g3), where g = g1 + g ...
In this paper we study the limiting achievable coverage problems of sensor networks. For the sensor networks with uniform distributions we obtain a complete characterization of the coverage probability. For the sensor networks with non-uniform distributions, we derive two different necessary and sufficient conditions respectively in the situations that the density function achieves its minimum value...
In this paper some new results on edge coloring of graphs are introduced. This paper deals mainly with edge cover coloring, g-edge cover coloring, (g, f)-coloring and equitable edge coloring. Some new problems and conjectures are presented.
For a graph G, the total graph T(G) of G is the graph with vertex set V(G) ∪ E(G) in which the vertices x and y are joined by an edge if x and y are adjacent or incident in G. In this paper, we show that the complement of total graph T(G) of a simple graph G is hamiltonian if and only if G is not isomorphic to any graph in {K1, r| r ≥ 1} ∪ {K1, s + K ...
Let G be a graph with vertex set V(G) and edge set E(G). The isolated toughness of G is defined as I(G) = min{|S|/i(G − S) | S ⊆ V(G), i(G − S) ≥ 2} if G is not complete; otherwise, set I(G) = |V(G)| − 1. Let f and g be two nonnegative integer-valued functions defined on V(G) satisfying a ≤ g(x) ≤ f(x) ≤ b . The purpose in this paper are to present sufficient conditions in terms of the isolated toughness...
The integrity I(G) of a noncomplete connected graph G is a measure of network invulnerability and is defined by I(G) = min {|S| + m(G − S)}, where S and m(G − S) denote the the subset of V and the order of the largest component of G − S, respectively. In this paper, we determine the integrity and some other parameters of middle graphs of some classes of graphs.
We prove that for every k > 1, there exist k-fold coverings of the plane (1) with strips, (2) with axis-parallel rectangles, and (3) with homothets of any fixed concave quadrilateral, that cannot be decomposed into two coverings. We also construct, for every k > 1, a set of points P and a family of disks in the plane, each containing at least k elements of P, such that no matter how...
Bau and Beineke [2] asked the following questions: 1 Which cubic graphs G of order 2n have decycling number $\phi(G)= \lceil\frac{n+1}{2}\rceil$ ? 1 Which cubic planar graphs G of order 2n have decycling number $\phi(G)=\lceil\frac{n+1}{2}\rceil$ ? We answered the first question in [10]. In this paper we prove that if ${{\cal{P}}}(3^{2n})$ is the class of...
The definitions of quasilocally connected graphs, almost locally connected graphs and triangularly connected graphs are introduced by Zhang, Teng and Lai et al. They are all different extensions of locally connected graphs. Many known results on the condition of local connectivity have been extended to these weaker conditions mentioned above. In this paper, we study the relations among these different...
Let P be a set of n points in a metric space. A Steiner Minimal Tree (SMT) on P is a shortest network interconnecting P while a Minimum Spanning Tree (MST) is a shortest network interconnecting P with all edges between points of P. The Steiner ratio is the infimum over P of ratio of the length of SMT over that of MST. Steiner ratio problem is to determine the value of the ratio. In this paper we consider...
Let Sn be the set of simple graphs on n vertices in which no two cycles have the same length. A graph G in Sn is called a simple maximum cycle-distributed graph (simple MCD graph) if there exists no graph G′ in Sn with |E(G′)| > |E(G)|. A planar graph G is called a generalized polygon path...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.